package org.gzc.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description: 图的创建实现 --- 邻接矩阵
 * @Author: guozongchao
 * @Date: 2020/8/18 19:30
 */
public class MGraph {
    private int n; // 顶点数n
    private String[] vertexes; // 顶点列表
    private int[][] edges;  //边的邻接矩阵
    private boolean[] visited;  //标记顶点已访问

    public MGraph(int n) {
        this.n = n;
        this.edges = new int[n][n];
        this.vertexes = new String[n];
        this.visited = new boolean[n];
        System.out.println(Arrays.toString(visited));
    }

    public void initVertex(String[] vertexes) {
        this.vertexes = vertexes;
    }

    /**
     * 建立边 --- 带权值
     *
     * @param vertex1 顶点1
     * @param vertex2 顶点2
     * @param weight  边的权值
     */
    public void initEdges(String vertex1, String vertex2, int weight) {
        int v1 = -1;
        int v2 = -1;
        for (int i = 0; i < n; i++) {
            if (vertexes[i].equals(vertex1)) {
                v1 = i;
                continue;
            }
            if (vertexes[i].equals(vertex2)) {
                v2 = i;
                continue;
            }
        }
        if (v1 != -1 && v2 != -1) {
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;   //有向图 删除该行即可
        }
    }

    /**
     * 建立边---不带权值
     *
     * @param vertex1 顶点1
     * @param vertex2 顶点2
     */
    public void initEdges(String vertex1, String vertex2) {
        initEdges(vertex1, vertex2, 1);
    }

    /**
     * 矩阵遍历显示
     */
    public void display() {
        System.out.println("图的矩阵遍历：");
        for (int[] e1 : edges) {
            for (int e2 : e1) {
                System.out.printf("%d\t", e2);
            }
            System.out.println();
        }
    }

    private void resetVisited() {
        for (int i = 0; i < visited.length; i++) {
            visited[i]=false;
        }
    }

    /**
     * 深度优先搜索
     * @param vertex  顶点的下标
     */
    private void dfs(int vertex) {
        System.out.print("("+vertex+","+vertexes[vertex]+") ");
        visited[vertex]=true;
        for (int i = 0; i < n; i++) {
            //当前顶点与其他顶点有通路，并且没有被访问
            if (edges[vertex][i] != 0 && !visited[i]) {
                dfs(i);  //递归遍历该顶点
            }
        }
    }
    public void dfs() {
        for (int i = 0; i < n && !visited[i]; i++) {
            dfs(i);
        }
        resetVisited();
    }

    /**
     * 广度优先搜索法
     * @param vertex  顶点的下标
     */
    private void bfs(int vertex) {
        int[] vertexQueue = new int[n];
        int front=0,rear=0;
        visited[vertex]=true;  //标记被访问
        //将该顶点入队
        vertexQueue[rear]=vertex;
        rear = (rear + 1) % n; //队尾指针后移

        while(front!=rear){  //当队列不为空
            //取出队头顶点
            int v=vertexQueue[front];
            front = (front + 1) % n; //队头指针后移
            System.out.print("("+vertex+","+vertexes[v]+") ");

            //遍历该顶点的所有邻接顶点，并入队
            for (int i = 0; i < n; i++) {
                if(edges[v][i] !=0 && !visited[i]){
                    visited[i]=true; //标记被访问
                    vertexQueue[rear]=i;
                    rear = (rear + 1) % n;
                }
            }
        }
    }

    public void bfs() {
        for (int i = 0; i < n && !visited[i]; i++) {
            bfs(i);
        }
        resetVisited();
    }

    public static void main(String[] args) {
        MGraph mGraph=new MGraph(8);
        mGraph.initVertex(new String[]{"A", "B", "C", "D","E","F","G","H"});
        mGraph.initEdges("A", "C");
        mGraph.initEdges("A", "B");
        mGraph.initEdges("B", "D");
        mGraph.initEdges("B", "E");
        mGraph.initEdges("C", "F");
        mGraph.initEdges("C", "G");
        mGraph.initEdges("F", "G");
        mGraph.initEdges("D", "H");
        mGraph.initEdges("E", "H");

        mGraph.display();

        System.out.println("\n深度优先搜索：");
        mGraph.dfs();

        System.out.println("\n广度优先搜索：");
        mGraph.bfs();
    }
}
